Reaching consensus is an important component of many fault tolerant distributed systems. Consensus is used to maintain consistency among redundant copies of some state in a distributed system. If there is a failure that affects a part of the distributed system, redundancy guarantees that the system can continue to operate.
Some existing techniques for reaching consensus employ message passing among processes. These techniques are based on rounds. If an invocation of the technique by a process uses an “old” round, it may fail to determine a consensus value. Some other existing techniques for reaching consensus require some degree of synchrony between processes in a distributed system. Other existing techniques use an oracle to help processes reach consensus.
Another technique for reaching consensus employs randomization in which processes have random “coins” to determine execution of the technique. This technique relies on probability to reach consensus and, with a small probability, leaves open the possibility that consensus is never achieved.
Yet another technique for reaching consensus requires that special shared-memory instructions be available. Such shared-memory instructions include load-linked instructions, store-conditional instructions, compare-and-swap instructions, or some form of read-modify-write instructions.